/**
 *	@author: Kathleen Go
 *	date created: January 5, 2006
 *	version: 1.04
 *  modified: March 13, 2006
 */

package text.ia;

import java.util.Vector;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.StringTokenizer;

public class TExtAligner{
	private Vector vTokenSource;
	private Vector vTokenTarget;
	private Hashtable alignedWords;
	private Vector vAlignedWordSource;
	private Vector vAlignedWordTarget;
	private Vector vFinalTokenSource;
	private Vector vFinalTokenTarget;
	private TExtLexicon lexicon;
	private char cTarget;
	private Hashtable htCompound;
	private Hashtable htLookUp;
	
	private Vector vMonth1;	//Filipino
	private Vector vMonth2;	//English
	private Vector vTimeLabel1; //Filipino
	private Vector vTimeLabel2; //English
	
	private boolean isInInput;
	
	private Vector vTargetIndices;

	
	public TExtAligner(char cTarget){
		alignedWords = new Hashtable();
		vAlignedWordSource = new Vector(1);
		vAlignedWordTarget = new Vector(1);
		this.cTarget = cTarget;
		lexicon = new TExtLexicon(this.cTarget);
		htCompound = new Hashtable();
		htLookUp = new Hashtable();
		initMonths();
		initTimeLabels();
	}
	
	/**	Finds the alignment of words between the Source tokens (vSourceTokens)
	 *	and the Target tokens (vTargetTokens).
	 * 
	 *	Returns the {@link Hashtable} of aligned words.
	 *
	 *	@param vTokenSource a {@link Vector} representing the Source tokens to be aligned
	 *	@param vTokenTarget a {@link Vector} representing the Target tokens to be aligned
	 *	@param bFromInputAnalysis is a primitive boolean indicating if it is being used
	 *		in input analysis or in template refinement
	 *	@return the {@link Hashtable} containing the aligned tokens
	 *			a token from the Source is stored as a KEY
	 *			a KEY entry is a {@link String} consisting of the Source token
	 *			corresponding VALUEs are the matched tokens in the Target
	 *			a VALUE entry is a {@link Vector} consisting of at least 1 Target token {@link String}
	 */
	public Hashtable align(Vector vTokenSource, Vector vTokenTarget, boolean bFromInputAnalysis){
		String strTokens = "";
		String strTarget = "";
		int nCtr = 0;
		int nStart = 0;
		Vector vCandidateLookUp = new Vector(1);
		Vector vTokenSequence = new Vector(1);
		Vector vCompoundWords;
		Vector vCompoundTemp;
		Vector vSourceTemp;
		boolean bFound;
		boolean bPunctuation;
		int i;
		int k;
		char cFirst;
		int nTargetIndex = -1;
	

		vFinalTokenTarget = (Vector)vTokenTarget.clone();
		vFinalTokenSource = (Vector)vTokenSource.clone();
		
		alignedWords.clear();
		vAlignedWordSource.clear();
		vAlignedWordTarget.clear();
		vTargetIndices = new Vector(1);
		
		for(i = 0; i < vTokenSource.size(); i++){
			bPunctuation = false;
			strTokens = (String)vTokenSource.get(i);
			if(strTokens == null)
				continue;
			vCompoundWords = null;
			
			if(isPunctuation(strTokens))
				bPunctuation = true;
			
			if(!(strTokens.startsWith("[")) && !(strTokens.endsWith("]"))
				 && !(strTokens.contains(" ")) && !bPunctuation)
				vCompoundWords = lookUpCompound(strTokens);
			
			if(vCompoundWords == null){
				vCompoundWords = new Vector(1);
				vCompoundWords.add(strTokens);
			}
			if(!(vCompoundWords.contains(strTokens)))
				vCompoundWords.add(strTokens);

			String strTargetRank = idenRank(strTokens);
			if(!strTokens.contains(" "))
				vCompoundWords = filterCompoundWords(vCompoundWords, vTokenSource, i);

			vCompoundTemp = (Vector)vCompoundWords.clone();
			bFound = false;
			
			for(k = 0; k < vCompoundWords.size() && !bFound; k++){
				vCandidateLookUp = null;
				if(!bPunctuation){
					vCandidateLookUp = new Vector(1);
					vCandidateLookUp.add((String)vCompoundWords.get(k));
				}
				if(vCandidateLookUp != null){
					strTarget = (String)vCandidateLookUp.get(0);
					vTokenSequence = getTokenSequence(vTokenTarget, strTarget, strTokens, bFromInputAnalysis);
					if(vTokenSequence != null){
						nTargetIndex = ((Integer)vTokenSequence.remove(2)).intValue();
						vTokenTarget = (Vector)vTokenSequence.get(1);
						vTokenSequence.remove(1);
						bFound = true;
					}
				}
				vCompoundWords = (Vector)vCompoundTemp.clone();
			}
			if(!bFound){
				for(k = 0; k < vCompoundWords.size() && !bFound; k++){
					if(!bPunctuation){
						vCandidateLookUp = lookUpWord((String)vCompoundWords.get(k));

						if(strTargetRank != null)
							if(vCandidateLookUp == null){
								vCandidateLookUp = new Vector(2);
								vCandidateLookUp.add(strTargetRank);
								vCandidateLookUp.add(new Integer(1));
							}
							else
								vCandidateLookUp.add(vCandidateLookUp.size()-1,strTargetRank);	
					}
					else{
						vCandidateLookUp = new Vector(1);
						vCandidateLookUp.add(strTokens);
					}
					
					if(vCandidateLookUp != null){
						if(!bPunctuation){
							vCandidateLookUp = sort(vCandidateLookUp);
						}
						for(int j = 0; j < vCandidateLookUp.size() && !bFound; j++){
							strTarget = (String)vCandidateLookUp.get(j);
							cFirst = strTokens.charAt(0);
							if(Character.isUpperCase(cFirst)){
								cFirst = strTarget.charAt(0);
								if(strTarget.length() == 1)
									strTarget = "" + Character.toUpperCase(cFirst);
								else{
									strTarget = strTarget.substring(1);
									strTarget = "" + Character.toUpperCase(cFirst) + strTarget;
								}
							}
							vTokenSequence = getTokenSequence(vTokenTarget, strTarget, strTokens, bFromInputAnalysis);
							if(vTokenSequence != null){
								nTargetIndex = ((Integer)vTokenSequence.remove(2)).intValue();
								vTokenTarget = (Vector)vTokenSequence.get(1);
								vTokenSequence.remove(1);
								bFound = true;
							}
						}
					}
					vCompoundWords = (Vector)vCompoundTemp.clone();
				}
			}
			if(bFound){
				boolean bAdjust = true;
				
				if(strTokens.contains(" "))
					bAdjust = false;
					
				strTokens = (String)vCompoundTemp.get(k-1);
				if(bAdjust && (strTokens.split(" ")).length > 1){
					vFinalTokenSource = adjustTokens(vFinalTokenSource, strTokens, -1);
					i = i + ((strTokens.split(" ")).length-1);
				}
				
				vAlignedWordSource.add(strTokens);
				strTokens = (String)vTokenSequence.get(0);
				
				if(bAdjust && (strTokens.split(" ")).length > 1)
					vFinalTokenTarget = adjustTokens(vFinalTokenTarget, strTokens, nTargetIndex);
				vAlignedWordTarget.add(vTokenSequence.clone());
				vTargetIndices.add(new Integer(nTargetIndex));
			}
			else{
				strTokens = (String)vCompoundTemp.get(vCompoundTemp.size()-1);
				vTokenSequence = new Vector();
				vTokenSequence.add(null);
				vAlignedWordSource.add(strTokens);
				vAlignedWordTarget.add(vTokenSequence.clone());
				vTargetIndices.add(new Integer(-1));
			}
		}

	//time before data:  An ordinary day in July 4 pm.
	//dapat 4 pm but pede marecognize na July 4	
		idenTime(); //d makaka-identify if hindi aligned in the first place
		idenDate(); //same here. kelangan makta sa lexicon yun months and time labels
		idenCompoundPN();
		
		convertAlignedWordsToHash();
		System.out.println(alignedWords);
		return alignedWords;
	}
	
	/**	Returns the Vector of possible compound words that starts with the given (strTokens).
	 *	It first checks the Hashtable of compound words in case strTokens was already
	 *		looked up in the Lexicon.
	 *	For every strToken that is looked up in the Lexicon, it will be added in the
	 *		Hashtable in case strToken is encountered in the future.
	 */
	public Vector lookUpCompound(String strTokens){
		Vector vCompoundWords;
		
		Object oLookUp = htCompound.get(strTokens.toLowerCase());
		if(oLookUp == null){
			vCompoundWords = lexicon.lookupCompound(strTokens);
			if(vCompoundWords == null)
				htCompound.put(strTokens.toLowerCase(), new Vector());
			else
				htCompound.put(strTokens.toLowerCase(), vCompoundWords.clone());
		}
		else if(((Vector)oLookUp).size() == 0){
			vCompoundWords = null;
		}
		else{
			vCompoundWords = (Vector)oLookUp;
		}
		if(vCompoundWords == null)
			return null;
		return (Vector)vCompoundWords.clone();
	}
	
	/**	Returns the Vector possible translations of the given (strWord).
	 *	It first checks the Hashtable of translations in case strWord was already
	 *		looked up in the Lexicon.
	 *	For every strWord that is looked up in the Lexicon, it will be added in the
	 *		Hashtable in case strWord is encountered in the future.
	 */
	public Vector lookUpWord(String strWord){
		Vector vCandidateLookUp = null;
		
		Object oLookUp = htLookUp.get(strWord.toLowerCase());
		if(oLookUp == null){
			vCandidateLookUp = lexicon.lookupForAlignment(strWord);
			if(vCandidateLookUp == null)
				htLookUp.put(strWord.toLowerCase(), new Vector());
			else
				htLookUp.put(strWord.toLowerCase(), vCandidateLookUp.clone());
		}
		else if(((Vector)oLookUp).size() == 0){
			vCandidateLookUp = null;
		}
		else{
			vCandidateLookUp = (Vector)oLookUp;
		}
		
		if(vCandidateLookUp == null)
			return null;
		return (Vector)vCandidateLookUp.clone();
	}

	/** This initializes the months in Tagalog and English.
	 */
	public void initMonths(){
		vMonth1 = new Vector();
		vMonth1.add("Enero");
		vMonth1.add("Pebrero");
		vMonth1.add("Marso");
		vMonth1.add("Abril");
		vMonth1.add("Mayo");
		vMonth1.add("Hunyo");
		vMonth1.add("Hulyo");
		vMonth1.add("Agosto");
		vMonth1.add("Setyembre");
		vMonth1.add("Oktubre");
		vMonth1.add("Nobyembre");
		vMonth1.add("Disyembre");

		vMonth2 = new Vector();
		vMonth2.add("January");
		vMonth2.add("February");
		vMonth2.add("March");
		vMonth2.add("April");
		vMonth2.add("May");
		vMonth2.add("June");
		vMonth2.add("July");
		vMonth2.add("August");
		vMonth2.add("September");
		vMonth2.add("October");
		vMonth2.add("November");
		vMonth2.add("December");
	}
	
	/**	Checks if the given (strToCheck) is a month.
	 */
	public boolean isAMonth (String strToCheck)
	{
		for(Iterator it = vMonth1.iterator(); it.hasNext(); )
			if(((String)it.next()).compareToIgnoreCase(strToCheck) == 0)
				return true;
		for(Iterator it = vMonth2.iterator(); it.hasNext(); )
			if(((String)it.next()).compareToIgnoreCase(strToCheck) == 0)
				return true;
		return false;
	}
	
	/**	Checks if the given (strToCheck) is a day.
	 */
	public boolean isADay (String strToCheck)
	{
	 	int nLength = strToCheck.length();
	 	if(nLength > 0 && nLength < 3){
	 		for(int i = 0; i < nLength; i++)
	 			if(!Character.isDigit(strToCheck.charAt(i)))
	 				return false;
	 		return true;
	 	}
	 	return false;
	 }
	
	/**	Checks if the given (strToCheck) is a year.
	 */
	public boolean isAYear (String strToCheck)
	{
		int nLength = strToCheck.length();
		if (nLength == 4){		
			for (int i=0; i < nLength; i++)
				if (!Character.isDigit(strToCheck.charAt(i)))
					return false;
			return true;
		}
		return false;
	}
	
	/**	This function identifies dates among the aligned Source and Target tokens.
	 *	Below are examples of the allowed alignments:
	 *		Source			<->		Target
	 *		9 July 1983				9 Hulyo 1983
	 *		July 1983				Hulyo 1983
	 *		July 9, 1983			Hulyo 9, 1983
	 *		July 9					Hulyo 9
	 *	Dates from the Source can also be retained in the Target
	 *		as long as the format agrees with one of those presented above.
	 *		For example:
	 *			Source			<->		Target
	 *			9 July 1983				9 July 1983
	 */
	public void idenDate(){
		String currentWord;

		for (int j = 0; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			
			//  9 July 1983
			if (!(currentWord.contains(" ")) && isADay(currentWord)){
				if (j + 2 < vAlignedWordSource.size()){
					String strPossMonth = (String)vAlignedWordSource.get(j+1);
					String strPossYear = (String)vAlignedWordSource.get(j+2);
					if (!(strPossMonth.contains(" ")) && !(strPossYear.contains(" "))
						 && isAMonth(strPossMonth) && isAYear(strPossYear)){
						currentWord += " " + strPossMonth + " " + strPossYear;
						
						String strTarget;
						vCandidateTarget = new Vector(1);
						
						Vector vEquiv = lookUpWord(strPossMonth);
						
						if(vEquiv != null){
							if(vEquiv.get(vEquiv.size()-1) instanceof Integer)
								vEquiv.remove(vEquiv.size()-1);
							for(Iterator it = vEquiv.iterator(); it.hasNext(); ){
								strTarget = (String)vAlignedWordSource.get(j) + " " + it.next() + " " + strPossYear;
								vCandidateTarget.add(strTarget);
							}
						}
						vCandidateTarget.add(new String(currentWord));
					}
				}
			}
			lookForMoreAlignments(vCandidateTarget, j, currentWord, true);			
		}

		for (int j = 0; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			
			if (!(currentWord.contains(" ")) && isAMonth(currentWord)){
				if (j + 3 < vAlignedWordSource.size()){
					String strTemp1 = (String)vAlignedWordSource.get(j+1);
					String strTemp2 = (String)vAlignedWordSource.get(j+2);
					String strTemp3 = (String)vAlignedWordSource.get(j+3);
					
					//  July 9, 1983
					if (!(strTemp1.contains(" ")) && !(strTemp2.contains(" ")) && !(strTemp3.contains(" "))
						 && isADay(strTemp1) && strTemp2.equals(",") && isAYear(strTemp3)){
							
						currentWord += " " + strTemp1 + " " + strTemp2 + " " + strTemp3;

						String strTarget;
						vCandidateTarget = new Vector(1);
						
						Vector vEquiv = lookUpWord((String)vAlignedWordSource.get(j));
						
						if(vEquiv != null){
							if(vEquiv.get(vEquiv.size()-1) instanceof Integer)
								vEquiv.remove(vEquiv.size()-1);
							for(Iterator it = vEquiv.iterator(); it.hasNext(); ){
								strTarget = it.next() + " " + strTemp1 + " " + strTemp2 + " " + strTemp3;
								vCandidateTarget.add(strTarget);
							}
						}
						vCandidateTarget.add(new String(currentWord));
					}
				}
			}
			lookForMoreAlignments(vCandidateTarget, j, currentWord, true);			
		}

		for (int j = 0; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			
			if (!(currentWord.contains(" ")) && isAMonth(currentWord)){
				if (j + 3 < vAlignedWordSource.size()){
					String strTemp1 = (String)vAlignedWordSource.get(j+1);
					String strTemp2 = (String)vAlignedWordSource.get(j+2);
					String strTemp3 = (String)vAlignedWordSource.get(j+3);
					
					// July 9 (not yet the end of the sentence)
					if (!(strTemp1.contains(" ")) && isADay(strTemp1)){
						currentWord += " " + strTemp1;

						String strTarget;
						vCandidateTarget = new Vector(1);
						
						Vector vEquiv = lookUpWord((String)vAlignedWordSource.get(j));
						
						if(vEquiv != null){
							if(vEquiv.get(vEquiv.size()-1) instanceof Integer)
								vEquiv.remove(vEquiv.size()-1);
							for(Iterator it = vEquiv.iterator(); it.hasNext(); ){
								strTarget = it.next() + " " + strTemp1;
								vCandidateTarget.add(strTarget);
							}
						}
						vCandidateTarget.add(new String(currentWord));
					}
				}
			}
			lookForMoreAlignments(vCandidateTarget, j, currentWord, true);			
		}

		for (int j = 0; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			
			if (!(currentWord.contains(" ")) && isAMonth(currentWord)){
				if (j + 3 < vAlignedWordSource.size()){
					String strTemp1 = (String)vAlignedWordSource.get(j+1);
					String strTemp2 = (String)vAlignedWordSource.get(j+2);
					String strTemp3 = (String)vAlignedWordSource.get(j+3);
					
					// July 1983 (not yet the end of the sentence)
					if (!(strTemp1.contains(" ")) && isAYear(strTemp1)){
						currentWord += " " + strTemp1;

						String strTarget;
						vCandidateTarget = new Vector(1);
						
						Vector vEquiv = lookUpWord((String)vAlignedWordSource.get(j));
						
						if(vEquiv != null){
							if(vEquiv.get(vEquiv.size()-1) instanceof Integer)
								vEquiv.remove(vEquiv.size()-1);
							for(Iterator it = vEquiv.iterator(); it.hasNext(); ){
								strTarget = it.next() + " " + strTemp1;
								vCandidateTarget.add(strTarget);
							}
						}
						vCandidateTarget.add(new String(currentWord));
					}
				}
			}
			lookForMoreAlignments(vCandidateTarget, j, currentWord, true);			
		}
		
		for (int j = 0; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			
			if (!(currentWord.contains(" ")) && isAMonth(currentWord)){
				if (j + 1 < vAlignedWordSource.size()){
					String strTemp = (String)vAlignedWordSource.get(j+1);
					
					// July 9 (at the end of sentence)
					if (!(strTemp.contains(" ")) && isADay(strTemp)){
						currentWord += " " + strTemp;

						String strTarget;
						vCandidateTarget = new Vector(1);
						
						Vector vEquiv = lookUpWord((String)vAlignedWordSource.get(j));
						
						if(vEquiv != null){
							if(vEquiv.get(vEquiv.size()-1) instanceof Integer)
								vEquiv.remove(vEquiv.size()-1);
							for(Iterator it = vEquiv.iterator(); it.hasNext(); ){
								strTarget = it.next() + " " + strTemp;
								vCandidateTarget.add(strTarget);
							}
						}
						vCandidateTarget.add(new String(currentWord));
					}
				}
			}
			lookForMoreAlignments(vCandidateTarget, j, currentWord, true);			
		}
		
		for (int j = 0; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			
			if (!(currentWord.contains(" ")) && isAMonth(currentWord)){
				if (j + 1 < vAlignedWordSource.size()){
					String strTemp = (String)vAlignedWordSource.get(j+1);
					
					// July 1983 (at the end of sentence)
					if (!(strTemp.contains(" ")) && isAYear(strTemp)){
						currentWord += " " + strTemp;

						String strTarget;
						vCandidateTarget = new Vector(1);
						
						Vector vEquiv = lookUpWord((String)vAlignedWordSource.get(j));
						
						if(vEquiv != null){
							if(vEquiv.get(vEquiv.size()-1) instanceof Integer)
								vEquiv.remove(vEquiv.size()-1);
							for(Iterator it = vEquiv.iterator(); it.hasNext(); ){
								strTarget = it.next() + " " + strTemp;
								vCandidateTarget.add(strTarget);
							}
						}
						vCandidateTarget.add(new String(currentWord));
					}
				}
			}
			lookForMoreAlignments(vCandidateTarget, j, currentWord, true);			
		}
	}
	
	/**	This checks whether the Source tokens (currentWord) has an alignment in the
	 *		Target tokens given the possible Target alignments (vCandidateTarget).
	 *	The given integer j is used to indicate the starting index of currentWord in the
	 *		Vector of aligned Source tokens while the boolean isDate is used to identify
	 *		whether the tokens to be aligned are dates or not.
	 *	This is used by idenDate() and idenTime().
	 */
	public void lookForMoreAlignments(Vector vCandidateTarget, int j, String currentWord, boolean isDate){
		if(vCandidateTarget != null){
			boolean bFound = false;
			String strTarget = null;
			int nLimit = (new StringTokenizer(currentWord)).countTokens() + j - 1;
			Vector vTarget;
			
			for(int i = vCandidateTarget.size() - 1; i >= 0 && !bFound; i--){
				String[] strTokensCand = ((String)vCandidateTarget.get(i)).split(" ");
		
				boolean bMatch = true;
				
				for(int k = j; k <= nLimit && bMatch; k++){
					vTarget = (Vector)vAlignedWordTarget.get(k);
					if(vTarget.get(0)== null || ((String)vTarget.get(0)).compareToIgnoreCase(strTokensCand[k-j]) != 0)
						bMatch = false;
				}
				if(bMatch){
					bFound = true;
					strTarget = "";
					for(int k = j; k <= nLimit; k++){
						vTarget = (Vector)vAlignedWordTarget.get(k);
						strTarget = strTarget + " " + (String)vTarget.get(0); 
					}
					strTarget = strTarget.trim();
				}
			}
			
			if(bFound)
				updateTokens(currentWord, strTarget, nLimit, j, isDate);
		}
	}
	
	/**  If the Source token has a valid alignment (strTarget) among the Target tokens,
	 *		the Vector of Aligned tokens and the Vector of Final tokens will be updated
	 *		to recognize the new alignment.
	 *	The given integer j is used to indicate the starting index of currentWord in the
	 *		Vector of aligned Source tokens while the integer nLimit is used to indicate
	 *		the end index of currentWord.  The boolean isDate is used to identify
	 *		whether the tokens to be aligned are dates or not.
	 *	This is used by idenDate(), idenTime() and idenCompoundPN().
	 */
	public void updateTokens(String currentWord, String strTarget, int nLimit, int j, boolean isDate){
		boolean isInInputS;
		boolean isInInputT;
		Vector vTarget;
		
		Vector vFinalTokenSourceBU = (Vector)vFinalTokenSource.clone();
		Vector vFinalTokenTargetBU = (Vector)vFinalTokenTarget.clone();
		
		vFinalTokenSource = adjustTokens(vFinalTokenSource, currentWord, -1);
		isInInputS = isInInput;
		if(isDate)
			vFinalTokenTarget = adjustTokens(vFinalTokenTarget, strTarget, -1);
		else	
			vFinalTokenTarget = adjustTokens(vFinalTokenTarget, strTarget, ((Integer)vTargetIndices.get(j)).intValue());
		isInInputT = isInInput;
		
		if(isInInputS && isInInputT){
			int nTargetIndex = -999;
			for(int k = nLimit; k > j; k--){
				vAlignedWordSource.remove(k);
				vAlignedWordTarget.remove(k);
				nTargetIndex = ((Integer)vTargetIndices.remove(k)).intValue();
			}
			if(nTargetIndex != -999)
				adjustIndices(nTargetIndex, nLimit-j);
			vAlignedWordSource.setElementAt(currentWord, j);
			vTarget = new Vector();
			vTarget.add(strTarget);
			vAlignedWordTarget.setElementAt(vTarget, j);
		}
		else{
			vFinalTokenSource = (Vector)vFinalTokenSourceBU.clone();
			vFinalTokenTarget = (Vector)vFinalTokenTargetBU.clone();
		}
	}

	/**	Checks if the given (charToCheck) is a capital letter.
	 */
	public boolean isACapitalLetter (char charToCheck)
	{
		if (charToCheck >= 65 && charToCheck <= 90)
			return true;
		return false;
	}	

	/**	This function identifies compound proper nouns among the aligned Source 
	 *		and Target tokens.
	 *	Below are examples of the allowed alignments:
	 *		Source			<->		Target
	 *		Harry Potter			Harry Potter
	 *		Arabella W. Strange		Arabella W. Strange
	 *	This function only identifies compound proper nouns whose every token starts with a
	 *		capital letter.
	 *	The example below is not accepted:
	 *		Source					<->		Target
	 *		De La Salle University			Pamantasan ng De La Salle
	 */
	public void idenCompoundPN(){
		String currentWord;
		String nextWord;
		String strTarget;
		Object currTarget;
		boolean bFound;
		int nStart = -1;
		
		for (int j = 0; j < vAlignedWordSource.size(); j++){
			bFound = false;
			
			currentWord = (String)vAlignedWordSource.get(j);
			
			currTarget = ((Vector)vAlignedWordTarget.get(j)).get(0);
			
			if(currTarget == null || !isACapitalLetter(currTarget.toString().charAt(0))
				|| (currTarget.toString()).contains(" ") || isAMonth(currTarget.toString())
				|| isPunctuation(currTarget.toString()))
				continue;
			
			strTarget = currTarget.toString();
			
			if (isACapitalLetter(currentWord.charAt(0)) && !(currentWord.contains(" "))
				&& !isAMonth(currentWord) && !isPunctuation(currentWord)){
				nStart = j;
				while (j + 1 < vAlignedWordSource.size()){
					nextWord = (String)vAlignedWordSource.get(j+1);
					currTarget = ((Vector)vAlignedWordTarget.get(j+1)).get(0);
					
					if (!(nextWord.contains(" ")) && isACapitalLetter(nextWord.charAt(0))
						 && !isAMonth(nextWord) && !isPunctuation(nextWord) && currTarget != null
						 && !((currTarget.toString()).contains(" ")) && isACapitalLetter(currTarget.toString().charAt(0))
						 && !isAMonth(currTarget.toString()) && !isPunctuation(currTarget.toString())){
							currentWord += " " + nextWord;
							j++;
							strTarget += " " + currTarget.toString();
							bFound = true;
					}
					else
						break;
				}
			}
			if(bFound){
				int nLimit = (new StringTokenizer(currentWord)).countTokens() + nStart - 1;
				updateTokens(currentWord, strTarget, nLimit, nStart, false);
			}
		}
	}
	
	/** This initializes the time labels in Tagalog and English.
	 */
	public void initTimeLabels(){
		vTimeLabel1 = new Vector(5);
		vTimeLabel1.add("o'clock");
		vTimeLabel1.add("a.m.");
		vTimeLabel1.add("am");
		vTimeLabel1.add("p.m.");
		vTimeLabel1.add("pm");

		vTimeLabel2 = new Vector(7);
		vTimeLabel2.add("o'clock");
		vTimeLabel2.add("n.u.");
		vTimeLabel2.add("nu");
		vTimeLabel2.add("n.h.");
		vTimeLabel2.add("nh");
		vTimeLabel2.add("n.g.");
		vTimeLabel2.add("ng");
	}

	/**	Checks if the given (strToCheck) is a time.
	 *	Below are examples of valid times:
	 *		4
	 *		4:25
	 */
	public boolean isATime (String strToCheck)
	{
		if (strToCheck.length() == 1)
			if (Character.isDigit(strToCheck.charAt(0)) && strToCheck.charAt(0) != '0')
				return true;
		else if (strToCheck.length() == 2)
			if (strToCheck.charAt(0) == '1' && Character.isDigit(strToCheck.charAt(1)))
				return true;
		else if (strToCheck.length() == 4)
			if (Character.isDigit(strToCheck.charAt(0)) && strToCheck.charAt(1) == ':'
				&& Character.isDigit(strToCheck.charAt(2)) && Character.isDigit(strToCheck.charAt(3)))
				return true;
		else if (strToCheck.length() == 5)
			if (Character.isDigit(strToCheck.charAt(0)) && Character.isDigit(strToCheck.charAt(1))
				&& strToCheck.charAt(2) == ':' && Character.isDigit(strToCheck.charAt(3))
				&& Character.isDigit(strToCheck.charAt(4)))
				return true;

		return false;
	}

	/**	Checks if the given (strToCheck) is a time label.
	 */
	public boolean isATimeLabel (String strToCheck)
	{
		for(Iterator it = vTimeLabel1.iterator(); it.hasNext(); )
			if(((String)it.next()).compareToIgnoreCase(strToCheck) == 0)
				return true;
		for(Iterator it = vTimeLabel2.iterator(); it.hasNext(); )
			if(((String)it.next()).compareToIgnoreCase(strToCheck) == 0)
				return true;
		return false;
	}

	/**	This function identifies time among the aligned Source and Target tokens.
	 *	Below are examples of the allowed Time alignments:
	 *		Source			<->		Target
	 *		9:24 am					9:24 nu
	 *		4 pm					4 nh
	 *		9 pm					9 ng
	 *	Times from the Source can also be retained in the Target
	 *		as long as the format agrees with one of those presented above
	 *		or is one of the following:
	 *			Source			<->		Target
	 *			9 o'clock				9 o'clock
	 *			6 pm					6 pm
	 */
	public void idenTime(){
		String currentWord;
		String prevWord;
		String nextWord;
		
		for (int j = 1; j < vAlignedWordSource.size(); j++){
			currentWord = (String)vAlignedWordSource.get(j);
			Vector vCandidateTarget = null;
			if (isATimeLabel(currentWord)){
				prevWord = (String)vAlignedWordSource.get(j-1);
				if (isATime(prevWord)){
					currentWord = prevWord + " " + currentWord;

					Vector vEquivTimeLabel;
					vCandidateTarget = new Vector(1);
					
					String strTarget;
					vCandidateTarget.add(new String(currentWord));
					vEquivTimeLabel = lookUpWord((String)vAlignedWordSource.get(j));
					
					if(vEquivTimeLabel != null){
						if(vEquivTimeLabel.get(vEquivTimeLabel.size()-1) instanceof Integer)
							vEquivTimeLabel.remove(vEquivTimeLabel.size()-1);
						for(Iterator it = vEquivTimeLabel.iterator(); it.hasNext(); ){
							strTarget = prevWord + " " + (String)it.next();
							vCandidateTarget.add(new String(strTarget));
						}
					}
					vCandidateTarget.add(currentWord);
				}
			}
			lookForMoreAlignments(vCandidateTarget, j-1, currentWord, false);			
		}
	}
	
	/**	This function returns the valid translation of a Source token (strSource)
	 *		that is a rank.
	 *	Below are examples of the valid ranks:
	 *		Given		<->		Return
	 *		ika-9				9th
	 *		9th					ika-9
	 *	Word forms of numbers (e.g. nine, siyam) are not recognized.
	 */
	public String idenRank(String strSource){
		String strTarget = null;
		if(strSource.contains(" "))
			return strTarget;
		String strSubSource;
		if(cTarget == 'f' && strSource.toLowerCase().endsWith("th")){
			strSubSource = strSource.substring(0, strSource.length()-2);
			boolean isNumber = false;
			if(strSubSource.length() > 0)
				isNumber = true;
			for(int n = 0; n < strSubSource.length(); n++)
				if(!(Character.isDigit(strSubSource.charAt(n))))
					isNumber = false;
			if(isNumber)
				strTarget = "ika-" + strSubSource;
		}
		else if(cTarget == 'e' && strSource.toLowerCase().startsWith("ika-")){
			strSubSource = strSource.substring(4, strSource.length());
			boolean isNumber = false;
			if(strSubSource.length() > 0)
				isNumber = true;
			for(int n = 0; n < strSubSource.length(); n++)
				if(!(Character.isDigit(strSubSource.charAt(n))))
					isNumber = false;
			if(isNumber)
				strTarget = strSubSource + "th";
		}
		
		return strTarget;
	}
	
	/**	Checks if the given (strWord) is a punctuation mark.
	 */
	public boolean isPunctuation(String strWord){
		
		if(strWord.equals(",") || strWord.equals("!") || strWord.equals(";") || strWord.equals("(")
			 || strWord.equals(")") || strWord.equals("{") || strWord.equals("}") || strWord.equals("[")
			  || strWord.equals("]") || strWord.equals("\"") || strWord.equals("<") || strWord.equals(">")
			   || strWord.equals("?") || strWord.equals("/") || strWord.equals(".") || strWord.equals("..."))
			   	return true;
		return false;
	}
	
	/**	Given the possible translations (vCandidateLookUp) of a certain Source token,
	 *		this function removes redundant words and sorts them according to the number
	 *		of tokens when tokenized according to white spaces.
	 *	Returns the Vector of sorted possible translations.
	 */
	public Vector sort(Vector vCandidateLookUp){
		Vector vTemp = (Vector)vCandidateLookUp.clone();
		int nSize = ((Integer)vCandidateLookUp.get(vCandidateLookUp.size()-1)).intValue();
		Vector vTokens = new Vector(1);
		Vector vFinal = new Vector(1);
		Iterator it;
		int nCandidate = vCandidateLookUp.size();
		boolean bFound;
		String strWord = null;
		
		int nTemp = 0;
		
		if(nCandidate > 2){
			vCandidateLookUp.clear();
			vCandidateLookUp.add((String)vTemp.get(0));
			
			if(nSize > 0)
				nTemp++;
				
			for(int i = 1; i < nCandidate - 1; i++){
				strWord = (String)vTemp.get(i);
				bFound = false;
				for(it = vCandidateLookUp.iterator(); it.hasNext() && !bFound; )
					if(strWord.compareTo((String)it.next()) == 0){
						bFound = true;
					}
				if(!bFound){
					vCandidateLookUp.add(strWord);
					if(i < nSize)
						nTemp++;					
				}
				
			}
			
			nSize = nTemp;
		}
		else
			vCandidateLookUp.remove(vCandidateLookUp.size()-1);

		vTemp = null;
		
		it = (vCandidateLookUp.subList(0, nSize)).iterator();		
		while(it.hasNext())
			vTokens.add(it.next());		
		vFinal.addAll(mergeSort(vTokens));
		
		vTokens.clear();
		
		it = (vCandidateLookUp.subList(nSize, vCandidateLookUp.size())).iterator();		

		while(it.hasNext())
			vTokens.add(it.next());		
		vFinal.addAll(mergeSort(vTokens));
		
		return vFinal;
	}

	/**	Returns the updated Source and Target tokens in the same order it was passed to the
	 *	align() function.  The Source and Target tokens returned may still be the same with
	 *	the original ones if there are no compound words, dates and times identified.
	 * 
	 *	Returns the {@link Vector} containing the Source tokens Vector
	 *		and Target tokens Vector.
	 *
	 *	@return the {@link Vector} containing the {@link Vector} of updated Source tokens and
	 *		{@link Vector} of updated Target tokens
	 *			index 0 contains the {@link Vector} of updated Source tokens
	 *			index 1 contains the {@link Vector} of updated Target tokens
	 */
	public Vector getUdpatedTokens(){
		Vector vUpdated = new Vector(2);
		vUpdated.add(vFinalTokenSource);
		vUpdated.add(vFinalTokenTarget);
		return vUpdated;
	}
	
	/**	Adjusts the given Vector of tokens (vFinalToken) such that tokens matching the
	 *		given token (strTokens) will be combined to a single token (or a single element
	 *		in vFinalToken).
	 *	The integer nStartIndex is used to indicate the starting index where strTokens
	 *		can be found in vFinalToken.  If nStartIndex = -1, this function justs looks
	 *		for strTokens in vFinalToken.
	 *	Returns the adjusted vFinalTokens.
	 */
	public Vector adjustTokens(Vector vFinalToken, String strTokens, int nStartIndex){
		StringTokenizer st = new StringTokenizer(strTokens);
		int nTokenCount = st.countTokens();
		boolean bMatch = true;
		boolean bFound = false;
		int nTokenIndex = 0;
		Vector vIndices = new Vector(1);
		
		String firstToken = st.nextToken();
		
		if(nStartIndex == -1){
			for(int i = 0; i < vFinalToken.size(); i++){
				String strFromFinal = (String)vFinalToken.get(i);
				if(strFromFinal != null && firstToken.equals(strFromFinal))
					vIndices.add(new Integer(i));
			}
		}
		else
			vIndices.add(new Integer(nStartIndex));
		
		for(int i = 0; i < vIndices.size() && !bFound; i++){
			int j = 0;
			st = new StringTokenizer(strTokens);
			if(((Integer)vIndices.get(i)).intValue() + st.countTokens() > vFinalToken.size())
				continue;
			while(st.hasMoreTokens() && bMatch){
				String strFromFinal = (String)vFinalToken.get(((Integer)vIndices.get(i)).intValue() + j);
				String strToken = st.nextToken();
				if(strFromFinal == null || !(strToken.equals(strFromFinal))){
					bMatch = false;					
					st = new StringTokenizer(strTokens);					
				}
				j++;
			}
			if(bMatch){
				bFound = true;
				for(int k = ((Integer)vIndices.get(i)).intValue() + nTokenCount - 1; k >= ((Integer)vIndices.get(i)).intValue(); k--)
					vFinalToken.remove(k);
				vFinalToken.insertElementAt(strTokens, ((Integer)vIndices.get(i)).intValue());
			}
			else
				bMatch = true;
		}
		
		isInInput = bFound;
		
		return vFinalToken;
	}
	
	/**	This removes the compound words (from vCompoundWords) that are not seen in the
	 *		Vector of Source tokens starting from the Source token pointed to by nStart.
	 *	Valid compound words always start with the Source token pointed to by nStart.
	 *	Returns the Vector of valid possible compound words.
	 */
	public Vector filterCompoundWords(Vector vCompoundWords, Vector vSource, int nStart){
		Vector vCompoundTokens;
		Vector vFinalCompound = new Vector(1);
		int nSource = vSource.size();
		int nCompoundToken;
		int nEnd;
		String strCompoundWord;
		String strCompoundSource;
		
		for(Iterator i = vCompoundWords.iterator(); i.hasNext(); ){
			String strCompWordOrig = (String)i.next();
			strCompoundWord = new String(strCompWordOrig);
		
			nCompoundToken = (strCompoundWord.split(" ")).length;
			nEnd = nStart + nCompoundToken;
			if(nEnd <= nSource){
				strCompoundSource = "";
				for(int j = nStart; j < nEnd; j++){
					if(j > nStart)
						strCompoundSource += " ";
					String strCompSrcTemp = (String)vSource.get(j);
					if(strCompSrcTemp == null || strCompSrcTemp.contains(" "))
						break;
					strCompoundSource += (String)vSource.get(j);
				}
				if(strCompoundSource.compareToIgnoreCase(strCompoundWord) == 0 && !(vFinalCompound.contains(strCompoundSource)))
					vFinalCompound.add(strCompoundSource);
			}
		}
		return mergeSort(vFinalCompound);
	}

	/**	Given a Vector of compound words (vCompoundWords), this function sorts them
	 *		according to the number of resulting tokens once these words are tokenized
	 *		according to white spaces.
	 *	Sorting is from the most number of tokens per word to the least.
	 *	Returns the Vector of sorted compound words.
	 */
	public Vector mergeSort(Vector vCompoundWords){
		Vector vLeft;
		Vector vRight;
		int nMiddle;
		
		if(vCompoundWords.size() <= 1)
			return vCompoundWords;
		else{
			vLeft = new Vector(1);
			vRight = new Vector(1);
			nMiddle = vCompoundWords.size()/2;
			for(int i = 0; i < nMiddle; i++)
				vLeft.add((String)vCompoundWords.get(i));
			for(int i = nMiddle; i < vCompoundWords.size(); i++)
				vRight.add((String)vCompoundWords.get(i));
			vLeft = mergeSort(vLeft);
			vRight = mergeSort(vRight);
			return merge(vLeft, vRight);
		}
	}
	
	/**	Given the two sets of words (vLeft and vRight), this function combines them
	 *		into a single Vector and at the same time, sorting the them according to
	 *		the number of resulting tokens when tokenized accoring to white spaces.
	 *	Sorting is from the most number of tokens per word to the least.
	 *	Returns the Vector of sorted words found in vLeft and vRight.
	 */
	public Vector merge(Vector vLeft, Vector vRight){
		int leftIndex = 0;
		int rightIndex = 0;
		int wholeIndex = 0;
		int restIndex;
		String strLeft;
		String strRight;
		Vector vWhole = new Vector(1);
		Vector vRest;
		int nLeftSize = vLeft.size();
		int nRightSize = vRight.size();
		int nRestSize;
		
		while (leftIndex < nLeftSize && rightIndex < nRightSize){
			strLeft = (String)vLeft.get(leftIndex);
			strRight = (String)vRight.get(rightIndex);
			
		    if ((strLeft.split(" ")).length > (strRight.split(" ")).length){
		    	vWhole.add(wholeIndex, strLeft);
				leftIndex++;
		    }
		    else{
		    	vWhole.add(wholeIndex, strRight);
				rightIndex++;
		    }
		    wholeIndex++;
		}
		
		if(leftIndex >= vLeft.size()){
		   vRest = vRight;
		   restIndex = rightIndex;
		}
		else{
		   vRest = vLeft;
		   restIndex = leftIndex;
		}
		nRestSize = vRest.size();
		for (int i = restIndex; i < nRestSize; i++){
			vWhole.add(wholeIndex, (String)vRest.get(i));
			wholeIndex++;
		}
    	return vWhole;
    }
	
	/**	Checks whether a candidate translation (strMatchedTarget) for a Source token can be
	 *		found in the Target tokens (vTarget).
	 *	The String strSourceToken is used to identify if the token was previously aligned
	 *		and composed of more than 1 tokens such that if it is, it is assumed that
	 *		strMatchedTarget can be seen in vTarget a single token only and since it has
	 *		already been aligned earlier.  This is used to accommodate the alignment of
	 *		tokens coming from templates retrieved from the Templates DB and which, 
	 *		already previously aligned.
	 *
	 *	Returns:
	 *		null if strMatchedTarget is not seen in the Target tokens
	 *		a Vector whose index 0 contains the modified vTarget wherein the tokens matching
	 *			strMatchedTarget is removed from the Vector of unaligned Target tokens.
	 *			Index 1 contains the starting index of the tokens matching strMatchedTarget.
	 */
	public Vector getTokenSequence(Vector vTarget, String strMatchedTarget, String strSourceToken, boolean bFromInputAnalysis){
		StringTokenizer st = new StringTokenizer(strMatchedTarget);
		int nMatch = st.countTokens();
		String strFirstToken = st.nextToken();
		Vector vIndices = new Vector(1);
		int nTarget = vTarget.size();
		
		int nIndex = 0;
		int nEnd = 0;
		int nFinish = -1;
		int nStart = -1;
		String strTarget;
		Vector vCandidate = new Vector(1);
		boolean bStop = false;;
		String strWord = null;
		
		if(!bFromInputAnalysis){
			int nRun = -1;
			int nIdentified = -1;
			for(Iterator it = vTarget.iterator(); it.hasNext(); ){
				nRun++;
				strTarget = (String)it.next();
				if(strTarget != null && strTarget.compareToIgnoreCase(strMatchedTarget) == 0){
					if(strTarget.compareTo(strMatchedTarget) == 0){
						bStop = true;
						nIdentified = nRun;
						strWord = null;
					}
					else 
						if(strWord == null){
							strWord = strTarget;
							nIdentified = nRun;
						}
				}
				if(bStop)
					break;
			}
			
			if(nIdentified != -1){
				vCandidate.add(vTarget.get(nIdentified));
				vTarget.setElementAt(null, nIdentified);
				vCandidate.add(vTarget);
				vCandidate.add(new Integer(nIdentified));
			}
			if(vCandidate.size() > 0)
				return vCandidate;
			else
				return null;
		}

		for(int i = 0; i < nTarget; i++){
			String strFromTarget = (String)vTarget.get(i);
			if(strFromTarget != null && strFirstToken.compareToIgnoreCase(strFromTarget) == 0)
				vIndices.add(new Integer(i));
		}

		for(Iterator it = vIndices.iterator(); it.hasNext(); ){
			nIndex = ((Integer)it.next()).intValue();
			nTarget = vTarget.size();
			nEnd = nIndex + nMatch;
			if(nEnd <= nTarget){
				strTarget = "";
				for(int i = nIndex; i < nEnd; i++){
					if(i > nIndex)
						strTarget += " ";
					String strTargetTemp = (String)vTarget.get(i);
					if(strTargetTemp == null || strTargetTemp.contains(" "))
						break;
					strTarget += vTarget.get(i);
				}
				if(strTarget.compareToIgnoreCase(strMatchedTarget) == 0){
					if(strTarget.compareTo(strMatchedTarget) == 0){
						vCandidate.add(strMatchedTarget);
						bStop = true;
						for(int k = nEnd-1; k > nIndex; k--)
							vTarget.remove(k);
						vTarget.setElementAt(null, nIndex);
						vCandidate.add(vTarget);
						vCandidate.add(new Integer(nIndex));
						adjustIndices(nIndex, nEnd-nIndex-1);
						strWord = null;
					}
					else
						if(strWord == null){
							strWord = strTarget;
							nFinish = nEnd;
							nStart = nIndex;
						}
						
					if(bStop)
						break;
				}
			}
		}
		
		if(strWord != null){
			vCandidate.add(strWord);
			for(int k = nFinish - 1; k > nStart; k--)
				vTarget.remove(k);		
			vTarget.setElementAt(null, nStart);
			vCandidate.add(vTarget);
			vCandidate.add(new Integer(nStart));
			adjustIndices(nIndex, nEnd-nIndex-1);
		}
		
		if(vCandidate.size() > 0)
			return vCandidate;					
		else
			return null;
	}

	/**	Adjusts the indices referring to the Target tokens whenever dates, times and
	 *		compound proper nouns are combined into 1 token.
	 *	The integer nStart is used to indicate the starting index of the combined tokens.
	 *		All indices greater than nStart pointing to Target tokens found after the
	 *		combined tokens will be reduced by the given offset (nOffset) which is the
	 *		number of combined tokens less 1.
	 */
	public void adjustIndices(int nStart, int nOffset){
		int nIndexSize = vTargetIndices.size();
		
		for(int i = 0; i < nIndexSize; i++){
			int nIndex = ((Integer)vTargetIndices.get(i)).intValue();
			if(nIndex > nStart)
				vTargetIndices.setElementAt(new Integer(nIndex-nOffset), i);
		}
	}
	
	/**	Converts the Vector of aligned Source and Target tokens to a Hashtable
	 *		wherein the Source token serves as KEYS while a Vector of
	 *		Target tokens serves as VALUES.
	 */
	public void convertAlignedWordsToHash(){
		Vector vTarget;
		Vector vTargetTemp;
		int nIndex = -1;
		Vector vIncluded = new Vector();
		String strIncluded = null;
		String strSource;
		int nSourceSize = vAlignedWordSource.size();
		int nIncludedSize;
		
		for(int i = 0; i < nSourceSize; i++){
			strSource = (String)vAlignedWordSource.get(i);
			vTarget = (Vector)vAlignedWordTarget.get(i);
			nIncludedSize = vIncluded.size();
			for(int j = 0; j < nIncludedSize; j++){
				strIncluded = (String)vIncluded.get(j);
				if(strIncluded.equals(strSource)){
					nIndex = j;
					break;					
				}
			}
			
			if(nIndex == -1){
				alignedWords.put(strSource, vTarget);
				vIncluded.add(strSource);
			}
			else{
				strSource = strIncluded;
				vTargetTemp = (Vector)alignedWords.get(strSource);
				vTargetTemp.add(vTarget.get(0));
				alignedWords.remove(strSource);
				alignedWords.put(strSource, vTargetTemp);
				nIndex = -1;
			}
		}
	}
}